from typing import List


class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        if not matrix:
            return 0

        def work(mm: List[List[int]], x: int) -> int:
            nn = len(mm)
            ans = 0
            i, j = nn - 1, 0
            while i >= 0 and j < nn:
                if mm[i][j] <= x:
                    ans += i + 1
                    j += 1
                else:
                    i -= 1
            return ans
        n = len(matrix)
        l, r = matrix[0][0], matrix[n-1][n-1]
        while l < r:
            h = (l + r) // 2
            hi = work(matrix, h)
            if hi >= k:
                r = h
            else:
                l = h + 1
        return l


solve = Solution()

questions = [
    (
        [[1,  5,  9], [10, 11, 13], [12, 13, 15]],
        8,
    ),
    (
        [[1, 2], [1, 3]],
        3,
    )
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q[0], q[1])
    print(f'ans: {solve.kthSmallest(q[0], q[1])}')

